import java.util.Arrays;

/**
 * @author tongchen
 * @create 2023-02-02 19:55
 */
public class Recursion {
    /*
    找重复：n*(n-1)的阶乘，n-1*n-2的阶乘......
    找变化：规模不断缩小
    找边界：当n=1时为边界
     */
    public static int f(int n){
        if(n==1){
            return 1;
        }
        return n*f(n-1);
    }

    /**打印i到j
     * 找重复：每次打印一个，从i到j
     * 找变化：规模不断变小
     * 找边界：当到达j时，打印最后一个
     *
     * @param i:初始值 j:最终值
     *
     */
    public static void print(int i,int j){
        if(i==j){
            //边界值
            System.out.println(j);
            return;
        }
        System.out.println(i);
        print(i+1, j);
    }

    /**
     * 数组求和
     * 找重复：每次求一个值，直到到数组的最后一个数
     * 找变化：规模逐渐变小
     * 找边界：当到数组的最后一个数时结束
     * @param
     */
    public static int calculateSum(int[]arr,int x){
        //边界 条件
        if(x== arr.length-1){
            return arr[arr.length-1];
        }
       return arr[x]+ calculateSum(arr, x+1);
    }

    /**
     * 反转字符串
     * 重复：每次反转一个
     * 变化：规模
     * 边界：到最后一个
     * @param
     */
    public static void reversel(String str,int x){
        if(x==0){
            System.out.print(str.charAt(0));
            return;
        }
        System.out.print(str.charAt(x));
        reversel(str, x-1);
    }

    /**
     *
     * @param x:求fib数列的num
     * @return
     */
    public static int fib(int x){
        if(x==1||x==2){
            return 1;
        }
        return fib(x-1)+fib(x-2);
    }
    public static int maxDivisor(int m,int n){
        if(n==0){
            return m;
        }
     return    maxDivisor(n, m%n);
    }
    public static void insertSort(int[]arr,int index){
        if(index==0){
            return;
        }
        insertSort(arr, index-1);
        int tmp=index-1;
        int num=arr[index];
        while(tmp>=0){
            if(arr[tmp]>num){
                arr[tmp+1]=arr[tmp];
                tmp--;
            }
            else{
                break;
            }
            arr[tmp+1]=num;
        }

    }
    public static void main(String[] args) {
        System.out.println(f(10));

        print(1, 10);
        System.out.println(calculateSum(new int[]{1, 2, 3, 4, 5}, 0));
        reversel(new String("ABCD"),3);
        System.out.println(fib(5));
        System.out.println(maxDivisor(9, 4));
        int[]arr={5,6,4,3,7,1};
        insertSort(arr, 5);
        System.out.println(Arrays.toString(arr));
    }

}
